package com.yx.study.leet.questionList.questionTwo;

import org.junit.Test;

/**
 * 55. 跳跃游戏
 * 中等
 * https://leetcode.cn/problems/jump-game/
 */
public class Solution55 {
    public boolean canJump(int[] nums) {
//        if(nums==null || nums.length==0) {
//            return true;
//        }
//        return getMax(0, nums[0], nums);
        return canJumpNation(nums);
    }

    private boolean getMax(int index, int num, int[] nums) {
        if (num <= 0) {
            return false;
        }
        int indexMax = index;
        int max = nums[index];
        for (int i = index + 1; i <= num; i++) {
            if (nums[i] >= max) {
                max = nums[i];
                indexMax = i;
            }
        }
        if(indexMax==index){
            return false;
        }
        if (indexMax != index && indexMax + nums[indexMax] +1< nums.length) {
            return getMax(indexMax, nums[indexMax], nums);
        }
        return true;
    }

    private boolean canJumpNation(int[] nums){ // TODO 55. 跳跃游戏 有没有一种情况,不是最大才能跳过陷阱? 暂未想到此场景如何设计
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; i++) {
            if (i<=rightmost){
                rightmost = Math.max(rightmost,i+nums[i]);
                if (rightmost>=n-1){
                    return true;
                }
            }
        }
        return false;
    }

    @Test
    public void test() {
        int[] nums = new int[]{2, 3, 1, 1, 4};
        nums = new int[]{3,2,1,0,4};
        nums = new int[]{0};
        System.out.println(canJump(nums));
    }

}
